package boboUtil;

import java.util.Arrays;
import java.util.ConcurrentModificationException;
import java.util.NoSuchElementException;

public class BoboArrayList<E> extends BoboAbstractList<E>
        implements BoboList<E>, java.io.Serializable {

    private static final long serialVersionUID = 8683452581122892189L;
    private static final int DEFAULT_CAPACITY = 10;
    private static final Object[] EMPTY_ELEMENTDATA = {};
    private static final Object[] DEFAULTCAPATACITY_EMPTY_ELEMENTDATA = {};
    private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

    //保存的数据
    transient Object[] elementData;

    private int size;

    //3个构造函数
    public BoboArrayList(){
        this.elementData = DEFAULTCAPATACITY_EMPTY_ELEMENTDATA;
    }

    public BoboArrayList(int initialCapacity){
        if (initialCapacity > 0){
            this.elementData = new Object[initialCapacity];
        } else if (initialCapacity == 0){
            this.elementData = EMPTY_ELEMENTDATA;
        } else {
            System.out.println("error: 容量不能小于0");
        }
    }

    public BoboArrayList(BoboCollection<? extends E> c){
        elementData = c.toArray();
        if ((size = elementData.length) != 0){
            if (elementData.getClass() != Object[].class){
                elementData = Arrays.copyOf(elementData, size, Object[].class);
            }
        } else {
            elementData = EMPTY_ELEMENTDATA;
        }
    }



    /*
    * 增加
    * */
    public boolean add(E e){
        ensureCapacityInternal(size+1);
        elementData[size++] = e;
        return true;
    }
    public void add(int index, E e) {
        rangeCheckForAdd(index);

        ensureCapacityInternal(size + 1);
        System.arraycopy(elementData, index, elementData, index+1, size-index);
        elementData[index] = e;
        size++;
    }
    public boolean addAll(BoboCollection<? extends E> c){
        Object[] a = c.toArray();
        int numNew = a.length;
        ensureCapacityInternal(size + numNew);
        System.arraycopy(a, 0, elementData, size, numNew);
        size += numNew;
        return (numNew != 0);
    }


    private void ensureCapacityInternal(int minCapacity){
        //确保添加的元素有地方存储，当第一次添加元素的时候size+1 的值是1，所以第一次添加的时候会将当前elementData数组的长度变为10：
        if (elementData == DEFAULTCAPATACITY_EMPTY_ELEMENTDATA){
            minCapacity = Math.max(minCapacity, DEFAULT_CAPACITY);
        }
        ensureExplicitCapacity(minCapacity);
    }

    /*
    * 将修改次数（modCount）自增1，判断是否需要扩充数组长度,判断条件就是用当前所需的数组最小长度与数组的长度对比，
    * 如果大于0，则增长数组长度。
    * */
    private void ensureExplicitCapacity(int minCapacity){
        modCount++;

        if (minCapacity > elementData.length){
            grow(minCapacity);
        }
    }

    private void grow(int minCapacity){
        int oldCapacity = elementData.length;
        //增大数组容量，扩大为原来的1.5倍。
        int newCapacity = oldCapacity + oldCapacity>>1;
        if (newCapacity < minCapacity) {
            //如果还不够，就直接等于需要的大小
            newCapacity = minCapacity;
        }
        if (newCapacity > MAX_ARRAY_SIZE){
            newCapacity = hugeCapacity(minCapacity);
        }
        elementData = Arrays.copyOf(elementData, newCapacity);
    }

    //得到所能得到的最大容量
    private static int hugeCapacity(int minCapacity){
        //整数溢出 overflow
        if (minCapacity < 0){
            System.out.println("error: 整数溢出");
            System.exit(1);
        }
        return (minCapacity > MAX_ARRAY_SIZE) ? Integer.MAX_VALUE : MAX_ARRAY_SIZE;
    }

    //get方法(查)
    public E get(int index) {
        rangeCheck(index);
        return (E)elementData[index];
    }

    //set方法（改）
    public E set(int index, E e) {
        rangeCheck(index);
        E oldValue = (E)elementData[index];
        elementData[index] = e;
        return oldValue;
    }


    /*删除*/
    //根据索引位置删除
    /*
    * 1）判断索引有没有越界
    * 2）自增修改次数
    * 3）将指定位置（index）上的元素保存到oldValue
    * 4）将指定位置（index）上的元素都往前移动一位
    * 5）将最后面的一个元素置空，好让垃圾回收器回收
    * 6）将原来的值oldValue返回
    * */
    public E remove(int index) {
        rangeCheck(index);

        modCount++;
        E oldValue = (E)elementData[index];

        int numMoved = size - index -1;
        if (numMoved > 0)
            System.arraycopy(elementData, index+1, elementData, index, numMoved);

        elementData[--size] = null; //clear to let gc do its work

        return oldValue;
    }
    //根据对象remove 只删除匹配的第一个
    public boolean remove(Object o){
        if (o == null){
            for (int i=0; i<size; i++)
                if (elementData[i] == null) {
                    fastRemove(i);
                    return true;
                }
        } else {
            for (int i=0; i<size; i++)
                if (o.equals(elementData[i])){
                    fastRemove(i);
                    return true;
                }
        }
        return false;
    }

    private void fastRemove(int index){
        modCount++;

        int numMoved = size - index -1;
        if (numMoved > 0)
            System.arraycopy(elementData, index+1, elementData, index, numMoved);

        elementData[--size] = null; //clear to let gc do its work
    }
    //是否包含
    public boolean contains(Object o){
        return indexOf(o) >= 0;
    }

    public int indexOf(Object o){
        if (o == null){
            for (int i=0; i<size; i++){
                if (elementData[i] == null)
                    return i;
            }
        } else {
            for (int i=0; i<size; i++){
                if (o.equals(elementData[i]))
                    return i;
            }
        }
        return -1;
    }

    //暂未实现
    public BoboList<E> subList(int fromIndex, int toIndex) {
        return null;
    }

    @Override
    public BoboListIterator<E> listIterator(int index) {
        if (index < 0 || index > size)  throw new IndexOutOfBoundsException("Index: "+index);
        return new ListItr(index);
    }

    public BoboListIterator<E> listIterator() {
        return listIterator(0);
    }

    public int size() {
        return size;
    }

    public void clear() {
        modCount++;

        // clear to let GC do its work
        for (int i = 0; i < size; i++)
            elementData[i] = null;

        size = 0;
    }

    //修改elementData的大小，让其减至size大小
    public void trimToSize(){
        modCount++;

        if (size < elementData.length){
            elementData = (size == 0)? EMPTY_ELEMENTDATA : Arrays.copyOf(elementData, size);
        }
    }

    private void rangeCheckForAdd(int index) {
        if (index > size || index < 0)
            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
    }

    private String outOfBoundsMsg(int index) {
        return "Index: "+index+", Size: "+size;
    }
    private void rangeCheck(int index) {
        if (index >= size)
            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
    }

    private class Itr implements BoboIterator<E> {

        int cursor;         //指向下一个要处理的元素
        int lastRet = -1;   //指向上一次返回的元素，没有就是-1
        int expectedModCount = modCount;

        @Override
        public boolean hasNext() {
            return cursor != size;
        }

        @Override
        public E next() {
            checkForModification();
            int i = cursor;
            if (i >= size){
                throw new NoSuchElementException();
            }
            Object[] elementData = BoboArrayList.this.elementData;
            if (i >= elementData.length){
                throw new ConcurrentModificationException();
            }
            cursor = i+1;
            return (E) elementData[lastRet = i];
        }

        @Override
        public void remove() {
            if (lastRet < 0){
                System.out.println("error: lastRet < 0");
                return;
            }
            checkForModification();
            BoboArrayList.this.remove(lastRet);
            cursor = lastRet;
            lastRet = -1;
            expectedModCount = modCount;
        }

        final void checkForModification(){
            if (expectedModCount != modCount){
                System.out.println("error: expectedModCount != modCount");
                System.exit(1);
            }
        }
    }

    private class ListItr extends Itr implements BoboListIterator<E>{

        ListItr(int index){
            super();
            cursor = index;
        }
        @Override
        public boolean hasPrevious() {
            return cursor != 0;
        }

        @Override
        public E previous() {
            checkForModification();

            int i = cursor -1;
            if (i < 0)  throw new NoSuchElementException();
            Object[] elementData = BoboArrayList.this.elementData;
            if (i >= elementData.length) throw new ConcurrentModificationException();
            cursor = i;
            return (E) elementData[lastRet = i];
        }

        @Override
        public int nextIndex() {
            return cursor;
        }

        @Override
        public int previousIndex() {
            return cursor -1;
        }

        @Override
        public void set(E e) {
            if (lastRet < 0){
                System.out.println("error: lastRet < 0");
                return;
            }
            checkForModification();

            BoboArrayList.this.set(lastRet, e);

        }

        @Override
        public void add(E e) {
            checkForModification();

            int i = cursor;
            BoboArrayList.this.add(i, e);
            cursor = i+1;
            lastRet = -1;
            expectedModCount = modCount;
        }
    }

    private void writeObject(java.io.ObjectOutputStream s)
            throws java.io.IOException{
        int expectedModCount = modCount;
        s.defaultWriteObject();

        s.writeInt(size);

        for (int i=0; i<size; i++){
            s.writeObject(elementData[i]);
        }
        if (modCount != expectedModCount) {
            throw new ConcurrentModificationException();
        }
    }

    private void readObject(java.io.ObjectInputStream s)
            throws java.io.IOException, ClassNotFoundException {
        elementData = EMPTY_ELEMENTDATA;

        s.defaultReadObject();

        s.readInt();

        if (size > 0){
            ensureCapacityInternal(size);

            Object[] a = elementData;

            for (int i=0; i<size; i++){
                a[i] = s.readObject();
            }
        }

    }
}
